package com.togo.algorithm.medium.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author taiyn
 * @Description
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 *
 * @Date 下午5:30 2022/4/3
 **/
public class No22 {

    List<String> result = new ArrayList<>();

    /**
     * 回溯算法
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {

        backtrack(n, n, "");
        return result;
    }

    private void backtrack(int left, int right, String cur) {

        // 左括号肯定在前面才有效, 所以left必须小于right
        if(left > right) return;
        // 左括号在前
        if(left == 0 && right == 0) {
            result.add(cur);
            return;
        }

        // 必须保证先有左括号
        if(left > 0) {
            // 这里在退出递归后cur还是之前的cur, 所以不需要做回溯.
            backtrack(left - 1, right, cur + '(');
        }
        if(right > 0) {
            backtrack(left, right - 1, cur + ')');
        }
    }

    public List<String> generateParenthesisDynamic(int n) {


        return result;
    }

    public static void main(String[] args) {

        No22 no22 = new No22();
        no22.generateParenthesis(3);
    }
}
